%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input and output
\Require A Polish stack $P$ containing an arithmetic expression in
  reverse Polish notation.
\Ensure An evaluation of the arithmetic expression represented by $P$.
%%
%% algorithm body
\State $E \gets$ empty stack
\State $v \gets \MyNull$
\While{\rm $P$ is not empty}
  \State $x \gets \pop(P)$
  \If{\rm $x$ is an operator}
    \State $b \gets \pop(E)$
    \State $a \gets \pop(E)$
    \If{\rm $x$ is addition operator}
      \State $v \gets a + b$
    \ElsIf{\rm $x$ is subtraction operator}
      \State $v \gets a - b$
    \ElsIf{\rm $x$ is multiplication operator}
      \State $v \gets a \times b$
    \ElsIf{\rm $x$ is division operator}
      \State $v \gets a / b$
    \Else
      \State exit algorithm with error
    \EndIf
    \State $\push(E, v)$
  \Else
    \State $\push(E, x)$
  \EndIf
\EndWhile
\State $v \gets \pop(E)$
\State \Return $v$
\end{algorithmic}
